{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Profit in Job Scheduling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: jobScheduling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #规划兼职工作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你打算利用空闲时间来做兼职工作赚些零花钱。</p>\n",
    "\n",
    "<p>这里有&nbsp;<code>n</code>&nbsp;份兼职工作，每份工作预计从&nbsp;<code>startTime[i]</code>&nbsp;开始到&nbsp;<code>endTime[i]</code>&nbsp;结束，报酬为&nbsp;<code>profit[i]</code>。</p>\n",
    "\n",
    "<p>给你一份兼职工作表，包含开始时间&nbsp;<code>startTime</code>，结束时间&nbsp;<code>endTime</code>&nbsp;和预计报酬&nbsp;<code>profit</code>&nbsp;三个数组，请你计算并返回可以获得的最大报酬。</p>\n",
    "\n",
    "<p>注意，时间上出现重叠的 2 份工作不能同时进行。</p>\n",
    "\n",
    "<p>如果你选择的工作在时间&nbsp;<code>X</code>&nbsp;结束，那么你可以立刻进行在时间&nbsp;<code>X</code>&nbsp;开始的下一份工作。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/19/sample1_1584.png\" style=\"width: 300px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]\n",
    "<strong>输出：</strong>120\n",
    "<strong>解释：\n",
    "</strong>我们选出第 1 份和第 4 份工作， \n",
    "时间范围是 [1-3]+[3-6]，共获得报酬 120 = 50 + 70。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/19/sample22_1584.png\" style=\"height: 112px; width: 600px;\"> </strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]\n",
    "<strong>输出：</strong>150\n",
    "<strong>解释：\n",
    "</strong>我们选择第 1，4，5 份工作。 \n",
    "共获得报酬 150 = 20 + 70 + 60。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/19/sample3_1584.png\" style=\"height: 112px; width: 400px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= startTime.length == endTime.length ==&nbsp;profit.length&nbsp;&lt;= 5 * 10^4</code></li>\n",
    "\t<li><code>1 &lt;=&nbsp;startTime[i] &lt;&nbsp;endTime[i] &lt;= 10^9</code></li>\n",
    "\t<li><code>1 &lt;=&nbsp;profit[i] &lt;= 10^4</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-profit-in-job-scheduling](https://leetcode.cn/problems/maximum-profit-in-job-scheduling/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-profit-in-job-scheduling](https://leetcode.cn/problems/maximum-profit-in-job-scheduling/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,3]\\n[3,4,5,6]\\n[50,10,40,70]', '[1,2,3,4,6]\\n[3,5,10,6,9]\\n[20,20,100,70,60]', '[1,1,1]\\n[2,3,4]\\n[5,6,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n=len(startTime)\n",
    "        lst=sorted(range(n),key=lambda i:endTime[i])\n",
    "        f=list()\n",
    "        f.append(profit[lst[0]],)\n",
    "        for i in range(1,n):\n",
    "            c=lst[i]\n",
    "            j=len(f)//2\n",
    "            l,r=0,len(f)\n",
    "            while l<r:\n",
    "                mid=(l+r)//2\n",
    "                if endTime[lst[mid]]>startTime[c]:  r=mid\n",
    "                else:   l=mid+1\n",
    "            j=l-1\n",
    "            if j!=-1 and f[j]+profit[c]>f[-1]:\n",
    "                f.append(f[j]+profit[c],)\n",
    "            elif  j==-1 and profit[c]>f[-1]:\n",
    "                f.append(profit[c],)\n",
    "            else:\n",
    "                f.append(f[-1],)\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n = len(startTime)\n",
    "        jobs = sorted(zip(startTime, endTime, profit), key=lambda p: p[1])\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            k = bisect_right(jobs, jobs[i - 1][0], hi=i, key=lambda p: p[1])\n",
    "            dp[i] = max(dp[i - 1], dp[k] + jobs[i - 1][2])\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        jobs = sorted(zip(endTime, startTime, profit))\n",
    "        # print(jobs)\n",
    "        dp = [0] * (len(jobs) + 1)\n",
    "        for i in range(len(jobs)):\n",
    "            endTime, startTime, profit = jobs[i]\n",
    "            j = bisect_right(jobs, (startTime, inf), hi=i) #在jobs[:i]找到不大于startTime[i]的endTime[j]\n",
    "            dp[i+1] = max(dp[j] + profit, dp[i])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        #解题思路：\n",
    "        #对结束时间进行排序\n",
    "        #解析：动态规划+二分查找\n",
    "        #dp[i] = max(dp[i - 1],dp[k] + profit[i])\n",
    "\n",
    "        n = len(startTime)\n",
    "        jobs = [(start,end,pro) for start,end,pro in zip(startTime,endTime,profit)]\n",
    "        jobs.sort(key = lambda p : p[1])\n",
    "        dp = [0] * (n + 1) \n",
    "        endTime = [i[1] for i in jobs]\n",
    "        # print(endTime)\n",
    "\n",
    "        for i in range(1,n + 1):\n",
    "            j = bisect.bisect_right(endTime,jobs[i - 1][0])\n",
    "            # print(jobs[i-1][0],j)\n",
    "            dp[i] = max(dp[i - 1],dp[j] + jobs[i - 1][2])\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n=len(startTime)\n",
    "        lst=sorted(range(n),key=lambda i:endTime[i])\n",
    "        f=list()\n",
    "        f.append((endTime[lst[0]],profit[lst[0]],),)\n",
    "        for i in range(1,n):\n",
    "            c=lst[i]\n",
    "            j=len(f)//2\n",
    "            l,r=0,len(f)\n",
    "            while l<r:\n",
    "                mid=(l+r)//2\n",
    "                if f[mid][0]>startTime[c]:  r=mid\n",
    "                else:   l=mid+1\n",
    "            j=l-1\n",
    "            if j!=-1 and f[j][1]+profit[c]>f[-1][1]:\n",
    "                f.append((endTime[c],f[j][1]+profit[c],),)\n",
    "            elif  j==-1 and profit[c]>f[-1][1]:\n",
    "                f.append((endTime[c],profit[c],),)\n",
    "            else:\n",
    "                f.append((endTime[c],f[-1][1],),)\n",
    "        return f[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, st: List[int], et: List[int], ps: List[int]) -> int:\n",
    "        \n",
    "        def df(st, et,ps):    \n",
    "            n = len(st)\n",
    "            jobs = [(st[i], et[i], ps[i]) for i in range(n)]\n",
    "            jobs.sort(key=lambda x: x[1])\n",
    "            f = [0] * (n)\n",
    "            f[0]=jobs[0][2]#首个节点被选，收益为自己\n",
    "            back=[0] * (n)   #回溯链条\n",
    "            back[0]=0#首个节点回溯自己\n",
    "            isChoosed=[0] *n #该节点加入的时候，最优解，该节点是否被选了，0没被选，1被选了。路径回溯的时候需要\n",
    "            isChoosed[0]=1 #首个节点被选\n",
    "\n",
    "            for i in range(1, n):\n",
    "                a, b, c = jobs[i]\n",
    "                #f[i] = max(f[i - 1], c)\n",
    "                if f[i-1]>c:#本届点不选\n",
    "                    f[i]=f[i-1]\n",
    "                    back[i]=i-1\n",
    "                else:#只选本届点\n",
    "                    f[i]=c\n",
    "                    back[i]=i\n",
    "                    isChoosed[i]=1#该节点加入的时候，最优解，该节点是否被选了，0没被选，1被选了。路径回溯的时候需要\n",
    "\n",
    "                l, r = 0, i-1\n",
    "                while l < r:\n",
    "                    mid = l + r + 1 >> 1#（l + r + 1）>> 1 是（l + r）>> 1 的向上取整\n",
    "                    if jobs[mid][1] <= a:\n",
    "                        l = mid\n",
    "                    else:\n",
    "                        r = mid - 1\n",
    "                #前序所有结束时间都大于当前的开始时间，则不需要选，选f[i-1]和c中最大的方案即可        \n",
    "                if jobs[r][1] <= a:\n",
    "                    #f[i] = max(f[i], f[r + 1] + c)\n",
    "                    if f[i]>f[r]+c:#保持前面的选择，条件的f[i]只可能是f[i-1] 。如果f[i]是c，这个条件不可能满足，因为f[r+1]>0\n",
    "                        f[i]=f[i]\n",
    "                        back[i]=back[i]#保持前面的选择，条件的f[i]只可能是f[i-1] ,结果也只能是f[i-1]\n",
    "                    else:#选择本节点+前面的一部分节点\n",
    "                        f[i]=f[r]+c\n",
    "                        back[i]=r\n",
    "                        isChoosed[i]=1#该节点加入的时候，最优解，该节点是否被选了，0没被选，1被选了。路径回溯的时候需要\n",
    "\n",
    "            print([\"jobs:\",jobs[:5]])#排序后的结果\n",
    "            #print([\"back:\",back])#每个节点的前序回溯节点\n",
    "            #print([\"isChoosed:\",isChoosed])#该节点加入的时候，最优解，该节点是否被选了，0没被选，1被选了。路径回溯的时候需要\n",
    "            #print([\"fn:\",f])#规划结果\n",
    "\n",
    "            i=n-1\n",
    "            #if isChoosed[i]==1:\n",
    "            #    backlist.append(i)\n",
    "            while back[i]!=i:\n",
    "                i=back[i] \n",
    "                if isChoosed[i]==1:#节点被选才加进去\n",
    "                    backlist.append(i)\n",
    "            tmp=[jobs[i][2] for i in backlist]\n",
    "            print([\"规划路径：\",backlist[::-1],tmp[::-1],sum(tmp)])\n",
    "            return f[n-1]\n",
    "        backlist=[]#回溯链条    \n",
    "        return df(st,et,ps)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        startTime.insert(0,0)\n",
    "        endTime.insert(0,0)\n",
    "        profit.insert(0,0)\n",
    "        time = [[s,e,p] for (s,e),p in zip(zip(startTime, endTime), profit)]\n",
    "        time.sort(key = lambda x:(x[1],x[0]))\n",
    "        print(time)\n",
    "        dp = [0 for _ in range(len(endTime))]\n",
    "        sup = [0]\n",
    "        for i in range(len(time)):\n",
    "            s = time[i][0]\n",
    "            j = sup[-1]\n",
    "            if s<time[j+1][1]:\n",
    "                while s<time[j][1]:\n",
    "                    j-=1\n",
    "                sup.append(j)\n",
    "            else:\n",
    "                while s>=time[j+1][1]:\n",
    "                    j+=1\n",
    "                sup.append(j)\n",
    "        sup = sup[1:]\n",
    "        print(sup)\n",
    "        for i in range(1,len(time)):\n",
    "            s = time[i][0]\n",
    "            e = time[i][1]\n",
    "            p = time[i][2]\n",
    "            dp[i]=max(dp[i-1],dp[sup[i]]+p)\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, st: List[int], et: List[int], ps: List[int]) -> int:\n",
    "        \n",
    "        def df(st, et,ps):    \n",
    "            n = len(st)\n",
    "            jobs = [(st[i], et[i], ps[i]) for i in range(n)]\n",
    "            jobs.sort(key=lambda x: x[1])\n",
    "            f = [0] * (n)\n",
    "            f[0]=jobs[0][2]#首个节点被选，收益为自己\n",
    "            back=[0] * (n)   #回溯链条\n",
    "            back[0]=0#首个节点回溯自己\n",
    "            isChoosed=[0] *n #该节点加入的时候，最优解，该节点是否被选了，0没被选，1被选了。路径回溯的时候需要\n",
    "            isChoosed[0]=1 #首个节点被选\n",
    "            for i in range(1, n):\n",
    "                a, b, c = jobs[i]\n",
    "                #f[i] = max(f[i - 1], c)\n",
    "                if f[i-1]>c:#本届点不选\n",
    "                    f[i]=f[i-1]\n",
    "                    back[i]=i-1\n",
    "                else:#只选本届点\n",
    "                    f[i]=c\n",
    "                    back[i]=i\n",
    "                    isChoosed[i]=1#该节点加入的时候，最优解，该节点是否被选了，0没被选，1被选了。路径回溯的时候需要\n",
    "\n",
    "                l, r = 0, i-1\n",
    "                while l < r:\n",
    "                    mid = l + r + 1 >> 1#（l + r + 1）>> 1 是（l + r）>> 1 的向上取整\n",
    "                    if jobs[mid][1] <= a:\n",
    "                        l = mid\n",
    "                    else:\n",
    "                        r = mid - 1\n",
    "                #前序所有结束时间都大于当前的开始时间，则不需要选，选f[i-1]和c中最大的方案即可        \n",
    "                if jobs[r][1] <= a:\n",
    "                    #f[i] = max(f[i], f[r + 1] + c)\n",
    "                    if f[i]>f[r]+c:#保持前面的选择，条件的f[i]只可能是f[i-1] 。如果f[i]是c，这个条件不可能满足，因为f[r+1]>0\n",
    "                        f[i]=f[i]\n",
    "                        back[i]=back[i]#保持前面的选择，条件的f[i]只可能是f[i-1] ,结果也只能是f[i-1]\n",
    "                    else:#选择本节点+前面的一部分节点\n",
    "                        f[i]=f[r]+c\n",
    "                        back[i]=r\n",
    "                        isChoosed[i]=1#该节点加入的时候，最优解，该节点是否被选了，0没被选，1被选了。路径回溯的时候需要\n",
    "\n",
    "            \n",
    "            print([\"jobs:\",jobs])#排序后的结果\n",
    "            print([\"back:\",back])#每个节点的前序回溯节点\n",
    "            print([\"isChoosed:\",isChoosed])#该节点加入的时候，最优解，该节点是否被选了，0没被选，1被选了。路径回溯的时候需要\n",
    "            print([\"fn:\",f])#规划结果\n",
    "            i=n-1\n",
    "            #if isChoosed[i]==1:\n",
    "            #    backlist.append(i)\n",
    "            while back[i]!=i:\n",
    "                i=back[i] \n",
    "                if isChoosed[i]==1:#节点被选才加进去\n",
    "                    backlist.append(i)\n",
    "            tmp=[jobs[i][2] for i in backlist]\n",
    "            print([\"规划路径：\",backlist,tmp,sum(tmp)])\n",
    "            return f[n-1]\n",
    "        backlist=[]#回溯链条    \n",
    "        return df(st,et,ps)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n=len(profit)\n",
    "        info=sorted([(e,s,i) for s,e,i in zip(startTime,endTime,list(range(n)))])\n",
    "        end=[e for e,s,i in info]\n",
    "        dp=[[0,0] for _ in range(n)]\n",
    "        dp[0][0]=0\n",
    "        dp[0][1]=profit[info[0][2]]\n",
    "        ans=dp[0][1]\n",
    "        for i in range(1,n):\n",
    "            st=info[i][1]\n",
    "            j=bisect.bisect_right(end[:i],st)\n",
    "            dp[i][0] = max(dp[i-1])\n",
    "            if j==0:\n",
    "                dp[i][1]=profit[info[i][2]]\n",
    "            else:\n",
    "                dp[i][1]=max(dp[j-1])+profit[info[i][2]]\n",
    "        return max(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, st: List[int], et: List[int], ps: List[int]) -> int:\n",
    "        def df(st, et,ps):    \n",
    "            n = len(li)\n",
    "            #jobs = [(st[i], et[i], ps[i]) for i in range(n)]\n",
    "            #jobs.sort(key=lambda x: x[1])\n",
    "            f = [0] * (n)\n",
    "            f[0]=li[0][2]#jobs[0][2]#首个节点被选，收益为自己\n",
    "            back=[0] * (n)   #回溯链条\n",
    "            back[0]=0#首个节点回溯自己\n",
    "            isChoosed=[0] *n #该节点加入的时候，最优解，该节点是否被选了，0没被选，1被选了。路径回溯的时候需要\n",
    "            isChoosed[0]=1 #首个节点被选\n",
    "\n",
    "            for i in range(1, n):\n",
    "                a, b, c =li[i][4],li[i][5],li[i][2] #jobs[i]\n",
    "                #f[i] = max(f[i - 1], c)\n",
    "                if f[i-1]>c:#本届点不选\n",
    "                    f[i]=f[i-1]\n",
    "                    back[i]=i-1\n",
    "                else:#只选本届点\n",
    "                    f[i]=c\n",
    "                    back[i]=i\n",
    "                    isChoosed[i]=1#该节点加入的时候，最优解，该节点是否被选了，0没被选，1被选了。路径回溯的时候需要\n",
    "\n",
    "                l, r = 0, i-1\n",
    "                while l < r:\n",
    "                    mid = l + r + 1 >> 1#（l + r + 1）>> 1 是（l + r）>> 1 的向上取整\n",
    "                    if li[mid][5] <= a:\n",
    "                        l = mid\n",
    "                    else:\n",
    "                        r = mid - 1\n",
    "                #前序所有结束时间都大于当前的开始时间，则不需要选，选f[i-1]和c中最大的方案即可        \n",
    "                if li[r][5] <= a:\n",
    "                    #f[i] = max(f[i], f[r + 1] + c)\n",
    "                    if f[i]>f[r]+c:#保持前面的选择，条件的f[i]只可能是f[i-1] 。如果f[i]是c，这个条件不可能满足，因为f[r+1]>0\n",
    "                        f[i]=f[i]\n",
    "                        back[i]=back[i]#保持前面的选择，条件的f[i]只可能是f[i-1] ,结果也只能是f[i-1]\n",
    "                    else:#选择本节点+前面的一部分节点\n",
    "                        f[i]=f[r]+c\n",
    "                        back[i]=r\n",
    "                        isChoosed[i]=1#该节点加入的时候，最优解，该节点是否被选了，0没被选，1被选了。路径回溯的时候需要\n",
    "\n",
    "            print([\"jobs:\",li[:5]])#排序后的结果\n",
    "            print([\"back:\",back])#每个节点的前序回溯节点\n",
    "            print([\"isChoosed:\",isChoosed])#该节点加入的时候，最优解，该节点是否被选了，0没被选，1被选了。路径回溯的时候需要\n",
    "            print([\"fn:\",f])#规划结果\n",
    "\n",
    "            i=n-1\n",
    "            #if isChoosed[i]==1:\n",
    "            #    backlist.append(i)\n",
    "            while back[i]!=i:\n",
    "                i=back[i] \n",
    "                if isChoosed[i]==1:#节点被选才加进去\n",
    "                    backlist.append(i)\n",
    "            tmp=[li[i][2] for i in backlist]\n",
    "            print([\"规划路径：\",backlist[::-1],tmp[::-1],sum(tmp)])\n",
    "            return f[n-1]\n",
    "        backlist=[]#回溯链条\n",
    "        #适配期货版本\n",
    "        li=[]*len(st)\n",
    "        for i in range(len(st)):\n",
    "            li.append((i,\"sc\",ps[i],1,st[i],et[i]))\n",
    "        li=sorted(li,key=lambda x:x[5])    #一定要排序\n",
    "        print(li[:])    \n",
    "        return df(st,et,ps)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n = len(startTime)\n",
    "        dp = [0]\n",
    "        groups = defaultdict(list)\n",
    "        # for start, end, tip in rides:\n",
    "        #     groups[end].append([start, tip])\n",
    "        for i in range(n):\n",
    "            groups[endTime[i]].append([startTime[i], profit[i]])\n",
    "        ends = sorted(groups)\n",
    "\n",
    "        for end in ends:\n",
    "            dp.append(dp[-1])\n",
    "            for s, t in groups[end]:\n",
    "                j = bisect_right(ends, s)  # bisect_left >= s 的第一个下标\n",
    "                dp[-1] = max(dp[-1], dp[j] + t)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "\n",
    "        # dp[i] 表示在前 i 份兼职工作中做选择，能达到的最大收益是多少。\n",
    "        ## 那么就有，dp[0] = 0，因为第 0 份工作啥也没有，就是辅助的；\n",
    "        ## 且最终的结果是 dp[n]，也就是（前） n 份兼职工作中做选择，能达到的最大收益。\n",
    "        # 我们首先按工作结束时间排序。然后对于 dp[i]，其等于 max(dp[i-1], dp[k] + profit[i])。\n",
    "        ## 也就是 dp[i] 分为不包含 profit[i] 和包含 profit[i] 两种情况，在这两种中取最大值。\n",
    "        ## 不包含 profit[i] 的情况很好理解，包含 profit[i] 的情况则需要找到最晚的某个工作 k，\n",
    "        ## 使得 k 和 第 i 个工作在时间上没有冲突。而显然不能线性查找这个 k，只能用二分。\n",
    "\n",
    "        n = len(startTime)\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        # 为了在 for 循环中计算下一个 dp[i]，开始时间，结束时间和盈利都是不可缺少的，所以\n",
    "        ## 下面这个临时变量里这三个数组的元素都要。\n",
    "        tmp = sorted(zip(startTime, endTime, profit), key = lambda x : x[1])\n",
    "        # 还需要搞一个只包含结束时间的数组，二分查找的时候用。此外，光知道这个数组还不行，还得维护一个数组和索引的对应关系。\n",
    "        tmp2 = [tmp[i][1] for i in range(n)]\n",
    "        ddic = defaultdict(list)\n",
    "        for i, (_, etime, _) in enumerate(tmp):\n",
    "            ddic[etime].append(i+1)\n",
    "        # print(tmp, tmp2, ddic)\n",
    "        for i in range(1, n+1):\n",
    "            stime, _, prft = tmp[i-1]\n",
    "            ind = bisect.bisect_right(tmp2, stime)\n",
    "            if ind > 0:\n",
    "                lastPossibleEndtime = tmp2[ind-1]\n",
    "                # 万一不只一个这样的工作，取在 tmp 里排的最靠后的那个。\n",
    "                k = ddic[lastPossibleEndtime][-1]\n",
    "                dp[i] = max(dp[i-1], dp[k] + prft)\n",
    "            else:\n",
    "                dp[i] = max(dp[i-1], prft)\n",
    "        return dp[n]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        time = set(startTime + endTime)\n",
    "        time = list(time)\n",
    "        time.sort()\n",
    "        d = {k: v for v, k in enumerate(time)}\n",
    "        dp = [0] * len(time)\n",
    "        l = [(a, b, c) for a, b, c in zip(endTime, startTime, profit)]\n",
    "        l.sort()\n",
    "        print(l)\n",
    "        \n",
    "        lste = 0\n",
    "        for end, start, p in l:\n",
    "            s, e = d[start], d[end]\n",
    "            while lste < e:\n",
    "                lste += 1\n",
    "                dp[lste] = dp[lste-1]\n",
    "            if dp[e] < dp[s] + p:\n",
    "                dp[e] = dp[s] + p\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n = len(startTime)\n",
    "        values = list(zip(startTime, endTime, profit))\n",
    "        end_time_map = defaultdict(list)\n",
    "        max_end_time = 0\n",
    "        ans = 0\n",
    "        for value in values:\n",
    "            end_time_map[value[1]].append(value)\n",
    "            max_end_time = max(max_end_time, value[1])\n",
    "\n",
    "        \n",
    "        arr = [(-1, 0)]\n",
    "\n",
    "        def find_no_lt(end_time):\n",
    "            left, right = 0, len(arr) - 1\n",
    "            ans = 0\n",
    "            while left <= right:\n",
    "                middle = (left + right) // 2\n",
    "                if arr[middle][0] <= end_time:\n",
    "                    ans = middle\n",
    "                    left = middle + 1\n",
    "                else:\n",
    "                    right = middle - 1\n",
    "            return arr[ans][1]\n",
    "\n",
    "        last_max = 0\n",
    "        for end_time in sorted(end_time_map.keys()):\n",
    "            for value in end_time_map[end_time]:\n",
    "                last_max = max(last_max, find_no_lt(value[0]) + value[2])\n",
    "            arr.append((end_time, last_max))\n",
    "        return last_max\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n = len(startTime)\n",
    "        values = list(zip(startTime, endTime, profit))\n",
    "        end_time_map = defaultdict(list)\n",
    "        max_end_time = 0\n",
    "        ans = 0\n",
    "        for value in values:\n",
    "            end_time_map[value[1]].append(value)\n",
    "            max_end_time = max(max_end_time, value[1])\n",
    "\n",
    "        \n",
    "        arr = [(-1, 0)]\n",
    "\n",
    "        def find_no_lt(end_time):\n",
    "            left, right = 0, len(arr) - 1\n",
    "            ans = 0\n",
    "            while left <= right:\n",
    "                middle = (left + right) // 2\n",
    "                if arr[middle][0] <= end_time:\n",
    "                    ans = middle\n",
    "                    left = middle + 1\n",
    "                else:\n",
    "                    right = middle - 1\n",
    "            return arr[ans][1]\n",
    "\n",
    "        for end_time in sorted(end_time_map.keys()):\n",
    "            last_max = find_no_lt(end_time -1)\n",
    "            for value in end_time_map[end_time]:\n",
    "                new_max = find_no_lt(value[0]) + value[2]\n",
    "                ans = max(ans, new_max)\n",
    "                last_max = max(last_max, new_max)\n",
    "            arr.append((end_time, last_max))\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n = len(startTime)\n",
    "        job = [(startTime[i], endTime[i], profit[i]) for i in range(n)]\n",
    "        job.sort(key=lambda x: x[1])\n",
    "        allTime = sorted(startTime + endTime)\n",
    "        timeMap = dict()\n",
    "        for i, t in enumerate(allTime):\n",
    "            if i == 0 or allTime[i] != allTime[i - 1]:\n",
    "                timeMap[allTime[i]] = i \n",
    "        maxTime = len(allTime)\n",
    "        f = [0 for i in range(maxTime)]\n",
    "        cursor = 0\n",
    "        for i in range(maxTime):\n",
    "            if i > 0:\n",
    "                f[i] = f[i - 1]\n",
    "            while cursor < n and timeMap[job[cursor][1]] == i:\n",
    "                f[i] = max(f[i], f[timeMap[job[cursor][0]]] + job[cursor][2])\n",
    "                cursor += 1\n",
    "        return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n = len(startTime)\n",
    "        jobs = sorted(zip(startTime, endTime, profit), key=lambda p: p[1])\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            k = bisect_right(jobs, jobs[i - 1][0], hi=i, key=lambda p: p[1])\n",
    "            dp[i] = max(dp[i - 1], dp[k] + jobs[i - 1][2])\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        d_start = {}\n",
    "        d_end = defaultdict(list)\n",
    "        for l,r,p in zip(startTime,endTime,profit):\n",
    "            d_start[l] = 0\n",
    "            d_end[r].append([l,p])\n",
    "        last = 0\n",
    "        allt = list(set(startTime+endTime))\n",
    "        for t in sorted(allt):\n",
    "            if t in d_end:\n",
    "                last = max([last]+[d_start[l]+p for l, p in d_end[t]])\n",
    "            if t in d_start:\n",
    "                d_start[t] = last\n",
    "            # print(d_start, t, last)\n",
    "        return last\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict,deque\n",
    "from functools import cache\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        # dfs\n",
    "\n",
    "        ls = sorted(zip(startTime,endTime,profit))\n",
    "        startTime = [i[0] for i in ls]\n",
    "        endTime = [i[1] for i in ls]\n",
    "        profit = [i[2] for i in ls]\n",
    "        #ls = deque(startTime)\n",
    "        \n",
    "\n",
    "        n = len(startTime)\n",
    "        d = defaultdict(lambda:{})\n",
    "        for i in range(n):\n",
    "            d[startTime[i]][endTime[i]] = profit[i]\n",
    "\n",
    "        dp = defaultdict(lambda:0)\n",
    "\n",
    "        ls = deque()\n",
    "        \n",
    "        for i in d[startTime[-1]]:\n",
    "            dp[startTime[-1]] = max(d[startTime[-1]][i],dp[startTime[-1]])\n",
    "        \n",
    "        ls.append(startTime[-1])\n",
    "        last = dp[startTime[-1]]\n",
    "        #print(dp)\n",
    "        \n",
    "        for i in range(n-2,-1,-1):\n",
    "            if startTime[i] not in dp:\n",
    "                ls.appendleft(startTime[i])\n",
    "            for j in d[startTime[i]]:\n",
    "                ind = bisect.bisect_left(ls,j)\n",
    "                #print(ls,ind)\n",
    "                if ind >= len(ls):\n",
    "                    dp[startTime[i]] = max(dp[startTime[i]],d[startTime[i]][j])\n",
    "                else:\n",
    "                    dp[startTime[i]] = max(dp[startTime[i]],d[startTime[i]][j]+dp[ls[ind]])\n",
    "            dp[startTime[i]] = max(dp[startTime[i]],last)\n",
    "            last = dp[startTime[i]]\n",
    "            #print(startTime[i],dp[startTime[i]])\n",
    "\n",
    "        return dp[startTime[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "def max_profit(s: List[int], t: List[int], a: List[int]) -> int:\n",
    "    e = [s[i] + t[i] for i in range(len(s))]\n",
    "    e, s, t, a = zip(*sorted(zip(e, s, t, a)))\n",
    "    n = len(s)\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    \n",
    "    @functools.cache\n",
    "    def f(i):\n",
    "        if i < 0:\n",
    "            return 0\n",
    "        j = i - 1\n",
    "        while j >= 0 and s[j] + t[j] > s[i]:\n",
    "            j -= 1\n",
    "        ans = max(f(j) + a[i], f(i - 1))\n",
    "        print(i, ans)\n",
    "        return ans\n",
    "\n",
    "    return f(n - 1)\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        need_time = [endTime[i] - startTime[i] for i in range(len(startTime))]\n",
    "        print(need_time)\n",
    "        return max_profit(startTime, need_time, profit)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        \n",
    "        n = len(profit)\n",
    "\n",
    "        time = sorted(list(set(startTime + endTime)))\n",
    "        timeDict = dict()\n",
    "        for i, t in enumerate(time):\n",
    "            timeDict[t] = (i+1)\n",
    "\n",
    "\n",
    "\n",
    "        # start = min(startTime)\n",
    "        # startTime = [x-(start-1) for x in startTime]\n",
    "        # endTime = [x-(start-1) for x in endTime]\n",
    "        \n",
    "        startTime = [timeDict[x] for x in startTime]\n",
    "        endTime = [timeDict[x] for x in endTime]\n",
    "        start = 1\n",
    "        end = max(endTime)\n",
    "\n",
    "        # print (startTime, endTime)\n",
    "\n",
    "        dp = [0 for _ in range(end+1)]\n",
    "        candidates = [[] for _ in range(end+1)]\n",
    "\n",
    "        for i, s in enumerate(startTime):\n",
    "            candidates[s].append(i)\n",
    "\n",
    "        for e in range(end-1, 0, -1):\n",
    "            ans = dp[e+1]\n",
    "            for candidate in candidates[e]:\n",
    "                ans = max(ans, profit[candidate] + dp[endTime[candidate]])\n",
    "            dp[e] = ans\n",
    "\n",
    "\n",
    "\n",
    "        return dp[start]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n = len(startTime)\n",
    "        mp = {}\n",
    "        for i in range(n):\n",
    "            mp[startTime[i]] = 1\n",
    "            mp[endTime[i]] = 1\n",
    "        mp = {k: v for k, v in sorted(mp.items(), key=lambda item: item[0])}\n",
    "        cnt = 1\n",
    "        for k in mp:\n",
    "            mp[k] = cnt\n",
    "            cnt += 1\n",
    "        m = len(mp)\n",
    "        dp = [0]*(m+1)\n",
    "        r = [[] for i in range(m+1)]\n",
    "        for i in range(n):\n",
    "            r[mp[endTime[i]]].append([mp[startTime[i]],profit[i]])\n",
    "        num=  [0]*(m+1)\n",
    "        seg = FT(num)\n",
    "        for i in range(1,m+1):\n",
    "            for [l,w] in r[i]:\n",
    "                dp[i] = max(dp[i],seg.query(l)+w)\n",
    "            seg.update(i,dp[i])\n",
    "        return max(dp)\n",
    "class FT:\n",
    "    def __init__(self, nums):\n",
    "        self.n = len(nums)\n",
    "        self.tree = [float('-inf')] * (self.n + 1)\n",
    "        for i in range(1, self.n + 1):\n",
    "            self.update(i, nums[i-1])\n",
    "\n",
    "    def update(self, i, val):\n",
    "        while i <= self.n:\n",
    "            self.tree[i] = max(self.tree[i], val)\n",
    "            i += i & -i\n",
    "\n",
    "    def query(self, i):\n",
    "        res = float('-inf')\n",
    "        while i > 0:\n",
    "            res = max(res, self.tree[i])\n",
    "            i -= i & -i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n = len(startTime)\n",
    "        mp = {}\n",
    "        for i in range(n):\n",
    "            mp[startTime[i]] = 1\n",
    "            mp[endTime[i]] = 1\n",
    "        mp = {k: v for k, v in sorted(mp.items(), key=lambda item: item[0])}\n",
    "        cnt = 1\n",
    "        for k in mp:\n",
    "            mp[k] = cnt\n",
    "            cnt += 1\n",
    "        m = len(mp)\n",
    "        dp = [0]*(m+1)\n",
    "        r = [[] for i in range(m+1)]\n",
    "        for i in range(n):\n",
    "            r[mp[endTime[i]]].append([mp[startTime[i]],profit[i]])\n",
    "        mx = [0]*(m+1)\n",
    "        for i in range(1,m+1):\n",
    "            for [l,w] in r[i]:\n",
    "                dp[i] = max(dp[i],mx[l]+w)\n",
    "            mx[i]  =max(mx[i-1],dp[i])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        t_list = []\n",
    "        # s2job_list = defaultdict(list)\n",
    "        e2job_list = defaultdict(list)\n",
    "\n",
    "        for job in zip(startTime, endTime, profit):\n",
    "            s, e, p = job\n",
    "            t_list.extend([s, e])\n",
    "            # s2job_list[s].append(job)\n",
    "            e2job_list[e].append(job)\n",
    "        t_list.sort()\n",
    "        \n",
    "        t2ps = dict()\n",
    "        t2ps[0] = 0    # occ, not occ\n",
    "        lt = 0\n",
    "        for t in t_list:\n",
    "            max_ps = t2ps[lt]\n",
    "            for (s, _, p) in e2job_list[t]:\n",
    "                ps = t2ps[s] + p\n",
    "                if ps > max_ps:\n",
    "                    max_ps = ps\n",
    "            t2ps[t] = max_ps\n",
    "            \n",
    "            lt = t\n",
    "        return t2ps[lt]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        a=sorted(list(set(startTime+endTime)))\n",
    "        f=defaultdict(int)\n",
    "        g=defaultdict(list)\n",
    "        n=len(startTime)\n",
    "        for i in range(n):\n",
    "            g[endTime[i]].append([startTime[i],profit[i]])\n",
    "        m=len(a)\n",
    "        for i in range(m):\n",
    "            f[a[i]]=f[a[i-1]] if i>0 else 0\n",
    "            for [j,p] in g[a[i]]:\n",
    "                if f[j]+p>f[a[i]]:\n",
    "                    f[a[i]]=f[j]+p\n",
    "            #print(g[a[i]],a[i],f[a[i]])\n",
    "        return f[a[m-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        times = list(zip(startTime, endTime, profit))\n",
    "        times.sort(key=lambda x: x[1])\n",
    "        \n",
    "        def get_end_idx(target):\n",
    "            left = 0\n",
    "            right = len(times) - 1\n",
    "            \n",
    "            while left < right:\n",
    "                mid = (left + right + 1) // 2\n",
    "                if times[mid][1] > target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid\n",
    "            \n",
    "            return left\n",
    "\n",
    "        self.ans = 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx):\n",
    "            if idx < 0:\n",
    "                return 0\n",
    "            prev_idx = get_end_idx(times[idx][0])\n",
    "            if times[prev_idx][1] > times[idx][0]:\n",
    "                prev_idx = -1\n",
    "            \n",
    "            return max(self.ans, dfs(prev_idx) + times[idx][2])\n",
    "            \n",
    "        \n",
    "        # print(times)\n",
    "        self.ans = 0\n",
    "        for idx, ii in enumerate(times):\n",
    "            self.ans = max(self.ans, dfs(idx))\n",
    "        \n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        d={}\n",
    "        start=set(startTime)\n",
    "        end=set(endTime)\n",
    "        total=start.union(end)\n",
    "        n=len(total)\n",
    "        total=sorted(list(total))\n",
    "        for i,time in enumerate(total):\n",
    "            d[time]=i\n",
    "        dp=[0]*(n+1)\n",
    "        tmp=[[] for i in range(n+1)]\n",
    "        for s,e,p in zip(startTime,endTime,profit):\n",
    "            tmp[d[e]].append([d[s],p])\n",
    "        for i in range(1,n+1):\n",
    "            if i>1:\n",
    "                dp[i]=max(dp[i],dp[i-1])\n",
    "            for s,p in tmp[i]:\n",
    "                dp[i]=max(dp[i],dp[s]+p)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        time_to_new_time = {time: i for i, time in enumerate(sorted(startTime + endTime))}\n",
    "        startTime = [time_to_new_time[t] for t in startTime]\n",
    "        endTime = [time_to_new_time[t] for t in endTime]\n",
    "        end_to_profit = defaultdict(list)\n",
    "\n",
    "        for i in range(len(profit)):\n",
    "            st, ed, p = startTime[i], endTime[i], profit[i]\n",
    "            end_to_profit[ed].append((st, p))\n",
    "        N = len(startTime) * 2\n",
    "        f = [0 for _ in range(N + 10)]\n",
    "        for i in range(N):\n",
    "            f[i] = max(f[i], f[i - 1])\n",
    "            for start, p in end_to_profit[i]:\n",
    "                f[i] = max(f[i], f[start] + p)\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        # 线性DP 数据范围更大, \n",
    "        points = sorted(set(startTime + endTime))\n",
    "        N, L = len(startTime), len(points) \n",
    "        points = {points[i]:i for i in range(L)} \n",
    "        groups = {p:[] for p in range(L)} \n",
    "        for i in range(N): \n",
    "            groups[points[endTime[i]]].append((points[startTime[i]], profit[i])) \n",
    "        dp = [0] * (L+1) \n",
    "        # print(f\"points: {points}\")\n",
    "        for i in range(L): \n",
    "            dp[i+1] = dp[i] \n",
    "            for st, pf in groups[i]: \n",
    "                dp[i+1] = max(dp[i+1], dp[st+1] + pf) \n",
    "            # print(f\"i={i}, dp: {dp}\")\n",
    "        return dp[L] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        res=0\n",
    "        dic={}\n",
    "        n=len(startTime)\n",
    "        for i in range(0,n):\n",
    "            st=startTime[i]\n",
    "            ed=endTime[i]\n",
    "            if st not in dic.keys():\n",
    "                dic[st]=[0,[],[]]\n",
    "            dic[st][1].append(ed)\n",
    "            dic[st][2].append(profit[i])\n",
    "            if ed not in dic.keys():\n",
    "                dic[ed]=[0,[],[]]\n",
    "        arr=sorted(dic.keys())\n",
    "        for i in arr:\n",
    "            tmp=dic[i]\n",
    "            res=max(res,tmp[0])\n",
    "            lste=tmp[1]\n",
    "            lstp=tmp[2]\n",
    "            m=len(lste)\n",
    "            for j in range(0,m):\n",
    "                tg=lste[j]\n",
    "                dic[tg][0]=max(res+lstp[j],dic[tg][0])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        \"\"\" dfs记忆化递归 + 二分法查找\"\"\"\n",
    "        # 根据结束时间对 startTime, endTime, profit 进行排序\n",
    "        pairs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])\n",
    "        startTime, endTime, profit = zip(*pairs)\n",
    "\n",
    "        @cache\n",
    "        def dp(t):\n",
    "            # 如果输入t小于最小的结束时间, 返回0\n",
    "            if t < endTime[0]:\n",
    "                return 0\n",
    "\n",
    "            ans = 0\n",
    "\n",
    "            # 从当前t时刻往前搜索,\n",
    "            # 递推方程为:\n",
    "            #   若t不在endTime, dp(t) = dp(t_left_nearest_in_endTime)\n",
    "            #   若在, dp(t) = max(max(dp(start_i)+profit_i) ,dp(t_left_nearest_in_endTime))\n",
    "            #       其中start_i,profit_i是结束表中等于t的元素对于的起始时间和收益\n",
    "\n",
    "            # 查找结束点\n",
    "            # idx 为t在数组endTime中最右侧的位置, 若不存在则是第一个小于t的位置\n",
    "            idx = bisect.bisect_right(endTime, t) - 1\n",
    "            # 递推方程\n",
    "            for i in range(idx, -1, -1):\n",
    "                if endTime[i] != t:  # 若当前点不在结束表中, 返回t左侧第一个对应的值\n",
    "                    ans = max(ans, dp(endTime[i]))\n",
    "                    break\n",
    "                else:\n",
    "                    # 若在结束表中, 一直往左搜索, 取搜索的过程中的最大值返回\n",
    "                    ans = max(ans, dp(startTime[i]) + profit[i])\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return dp(endTime[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        \"\"\" dfs记忆化递归 + 二分法查找\"\"\"\n",
    "        \n",
    "        # 根据结束时间对 startTime, endTime, profit 进行排序\n",
    "        pairs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])\n",
    "        startTime, endTime, profit = zip(*pairs)\n",
    "\n",
    "        @cache\n",
    "        def dp(t):\n",
    "            # 如果输入t小于最小的结束时间, 返回0\n",
    "            if t < endTime[0]:\n",
    "                return 0\n",
    "\n",
    "            ans = 0\n",
    "\n",
    "            # 从当前t时刻往前搜索,\n",
    "            # 递推方程为:\n",
    "            #   若t不在endTime, dp(t) = dp(t_left_nearest_in_endTime)\n",
    "            #   若在, dp(t) = max(max(dp(start_i)+profit_i) ,dp(t_left_nearest_in_endTime))\n",
    "            #       其中start_i,profit_i是结束表中等于t的元素对于的起始时间和收益\n",
    "\n",
    "            # 查找结束点\n",
    "            # idx 为t在数组endTime中最右侧的位置, 若不存在则是第一个小于t的位置\n",
    "            idx = bisect.bisect_right(endTime, t) - 1\n",
    "            # 递推方程\n",
    "            for i in range(idx, -1, -1):\n",
    "                if endTime[i] != t:  # 若当前点不在结束表中, 返回t左侧第一个对应的值\n",
    "                    ans = max(ans, dp(endTime[i]))\n",
    "                    break\n",
    "                else:\n",
    "                    # 若在结束表中, 一直往左搜索, 取搜索的过程中的最大值返回\n",
    "                    ans = max(ans, dp(startTime[i]) + profit[i])\n",
    "            return ans\n",
    "        \n",
    "        return dp(endTime[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        # 压缩排序，保持原本的对应关系\n",
    "        jobs=sorted(zip(startTime,endTime,profit))\n",
    "        # print(z)\n",
    "        # startTime,endTime,profit=zip(*z)\n",
    "\n",
    "        end_start=jobs[-1][0]\n",
    "        dp=[0]*(end_start+1)\n",
    "        n=len(jobs)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            s1,s2=0,0\n",
    "            # 下一个start\n",
    "            if i+1<n:\n",
    "                s1=jobs[i+1][0]\n",
    "            # 找到大于或等于endTime[i]的start，使用二分查找\n",
    "            end_i=jobs[i][1]\n",
    "            l,r=i,n-1\n",
    "            while l<r:\n",
    "                mid=l+(r-l)//2\n",
    "                if jobs[mid][0]<end_i:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid\n",
    "            # print(l)\n",
    "            if jobs[l][0]>=end_i:\n",
    "                s2=jobs[l][0]\n",
    "            # print(s1,s2)\n",
    "            # 不打第i份工，选择从startTime[i]之后的工作s1开始\n",
    "            miss=dp[s1]\n",
    "            # 打第i份工，接着并从endTime[i]之后的工作s2开始\n",
    "            select=jobs[i][2] + dp[s2]\n",
    "            dp[jobs[i][0]]=max(dp[jobs[i][0]],miss,select)\n",
    "            \n",
    "        return dp[jobs[0][0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        \n",
    "        points = set(startTime + endTime)\n",
    "        points_list = list(points)\n",
    "        points_list.sort()\n",
    "        i2d = {}\n",
    "        d2i = {}\n",
    "        \n",
    "        for i, d in enumerate(points_list):\n",
    "            i2d[i] = d\n",
    "            d2i[d] = i\n",
    "        \n",
    "        data = defaultdict(list)\n",
    "        for i in range(len(startTime)):\n",
    "            s = startTime[i]\n",
    "            e = endTime[i]\n",
    "            p = profit[i]\n",
    "            data[e].append((s,p))\n",
    "\n",
    "    \n",
    "        N = len(points)\n",
    "        dp = [0] * (N+1)\n",
    "        for i in range(N):\n",
    "            dp[i+1] = dp[i]\n",
    "            d = i2d[i]\n",
    "            for s,p in data[d]:\n",
    "                si = d2i[s]\n",
    "                dp[i+1] = max(dp[i+1], dp[si+1]+p)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]):\n",
    "        mdict = {}\n",
    "        N = len(startTime)\n",
    "        startSet = set()\n",
    "        totalEnd = max(endTime)\n",
    "        for i in range(N):\n",
    "            arr = mdict.setdefault(startTime[i], [])\n",
    "            arr.append((endTime[i], profit[i]))\n",
    "            startSet.add(startTime[i])\n",
    "        startArr = list(startSet)\n",
    "        startArr.sort()\n",
    "        m = len(startArr)\n",
    "        @cache\n",
    "        def func(i): # 基于时间time的dp,找当前可选的选择一个或者一个都不选\n",
    "            if i >= totalEnd:\n",
    "                return 0\n",
    "            rst = 0\n",
    "            if i in mdict:\n",
    "                for end,p in mdict[i]: # mdict 是提前构建好的某一个时间开始的job\n",
    "                    v = p+func(end) # 选择其中一个\n",
    "                    if rst < v:\n",
    "                        rst = v\n",
    "            idx = bisect_left(startArr, i+1)\n",
    "            if idx < m:\n",
    "                v = func(startArr[idx]) # 一个都不选，二分查找找下一个跳的位置\n",
    "                if rst < v:\n",
    "                    rst = v\n",
    "            return rst\n",
    "        return func(1)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        job = {}\n",
    "        n = 0\n",
    "        for s, e, p in zip(startTime, endTime, profit):\n",
    "            job[e] = job.get(e, []) + [(s, p)]\n",
    "            n = max(n, e)\n",
    "        \n",
    "        # dp[i]: 到达i时间时的最大收益\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 0\n",
    "        for i in range(2, n + 1):\n",
    "            # 不做结束时间为i的工作\n",
    "            dp[i] = dp[i - 1]\n",
    "            # 做结束时间为i的工作\n",
    "            if i in job:\n",
    "                for s, e in job[i]:\n",
    "                    dp[i] = max(dp[i], dp[s] + e)\n",
    "        \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])\n",
    "        mapv = set()\n",
    "        for s, e, v in jobs:\n",
    "            mapv.add(s - 1)\n",
    "            mapv.add(s)\n",
    "            mapv.add(e - 1)\n",
    "            mapv.add(e)\n",
    "        maxLen = len(mapv)\n",
    "        mapv = { v:index + 1 for index, v in enumerate(sorted(mapv)) }\n",
    "        \n",
    "        groups = defaultdict(list)\n",
    "        for s ,e ,v in jobs:\n",
    "            s = mapv[s]\n",
    "            e = mapv[e]\n",
    "            groups[e].append((s, v))\n",
    "\n",
    "        dp = [0] * (maxLen + 2)\n",
    "        for e in range(1, maxLen + 2):\n",
    "            if e not in groups:\n",
    "                dp[e] = dp[e - 1]\n",
    "            else:\n",
    "                for s, v in groups[e]:\n",
    "                    dp[e] = max(dp[e], dp[s] + v, dp[e - 1])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 线段树，[s，t)\n",
    "class TreeNode:\n",
    "    def __init__(self, val, s, t):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.s = s\n",
    "        self.t = t\n",
    "    def __repr__(self):\n",
    "        return 'TreeNode({}, {}, {}, {}, {})'.format(self.val, self.s, self.t, self.left, self.right)\n",
    "\n",
    "    def update(self, i, val):\n",
    "        if self.s == self.t - 1:\n",
    "            assert self.s == i\n",
    "            self.val = val\n",
    "            return val\n",
    "\n",
    "        m = (self.s + self.t) // 2\n",
    "        if self.left is None:\n",
    "            self.left = TreeNode(0, self.s, m)\n",
    "            self.right = TreeNode(0, m, self.t)\n",
    "        if i < m:\n",
    "            v = self.left.update(i, val)\n",
    "        else:\n",
    "            v = self.right.update(i, val)\n",
    "        if v > self.val:\n",
    "            self.val = v\n",
    "        return self.val\n",
    "\n",
    "    def get(self, l, r):\n",
    "        #print(self, l, r)\n",
    "        if l <= self.s and self.t <= r:\n",
    "            return self.val\n",
    "        m = (self.s + self.t) // 2\n",
    "        mx = 0\n",
    "        if l < m and self.left and (tmp := self.left.get(l, r)) > mx:\n",
    "            mx = tmp\n",
    "        if r > m and self.right and (tmp := self.right.get(l, r)) > mx:\n",
    "            mx = tmp\n",
    "        return mx\n",
    "\n",
    "# class Solution:\n",
    "#     def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "#         dp = TreeNode(0, 0, max(nums) + 1)\n",
    "#         mx = dp.update(nums[0], 1)\n",
    "#         for i in nums[1:]:\n",
    "#             if (tmp := dp.update(i, dp.get(max(0, i - k), i) + 1)) > mx:\n",
    "#                 mx = tmp\n",
    "#         return mx\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        pm = {y: x for x, y in enumerate(sorted(set(startTime) | set(endTime)))}\n",
    "        sep = sorted((pm[s], pm[e], p) for s, e, p in zip(startTime, endTime, profit))\n",
    "        mx = 0\n",
    "        dp = TreeNode(0, 0, len(pm) + 1)\n",
    "        for s, e, p in sep:\n",
    "            tmp = dp.update(e, max(dp.get(0, e + 1), dp.get(0, s + 1) + p))\n",
    "            if tmp > mx:\n",
    "                mx = tmp\n",
    "        return mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution(object):\n",
    "    def jobScheduling(self, startTime, endTime, profit):\n",
    "        \"\"\"\n",
    "        :type startTime: List[int]\n",
    "        :type endTime: List[int]\n",
    "        :type profit: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #所有的endTime-1，就变成了一个左闭右闭的时间区间。\n",
    "        endTime = [x-1 for x in endTime]\n",
    "        alltime = sorted(np.unique(startTime+endTime))\n",
    "\n",
    "        #离散化，mp[i]表示原始的数字i离散化后的新结果\n",
    "        mp = {}\n",
    "        for t in alltime:\n",
    "            mp[t] = len(mp)\n",
    "            \n",
    "            \n",
    "        job_times = list(zip(startTime,endTime,profit))\n",
    "        \n",
    "        #把事件记录在event里，key是事件结束时间\n",
    "        event = {}\n",
    "        for start,end,pro in job_times:\n",
    "            start = mp[start]+1;\n",
    "            end = mp[end] + 1;\n",
    "            if not end in event:\n",
    "                event[end] = []\n",
    "            event[end].append([start,pro])\n",
    "        #动态规划过程\n",
    "        dp = np.zeros((len(mp)+2,),dtype=np.int32)\n",
    "        dp[0] = 0\n",
    "        ans = 0\n",
    "        for i in range(1,len(dp)):\n",
    "            #首先dp[i]至少是dp[i-1]\n",
    "            dp[i] = dp[i-1]\n",
    "            #如果i时刻有任务结束，可以触发相应转移\n",
    "            if i in event:\n",
    "                for start,pro in event[i]:\n",
    "                    dp[i] = max(dp[i],dp[start-1]+pro)\n",
    "            ans = max(ans,dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        import numpy\n",
    "        end = max(endTime)\n",
    "        dp = numpy.zeros(end+1,int)\n",
    "        li = []\n",
    "        for i in range(len(endTime)):\n",
    "            li.append([endTime[i],startTime[i],profit[i]])\n",
    "        li.sort()\n",
    "        # print(li)\n",
    "        pre = 0\n",
    "        for x, y, z in li:\n",
    "            dp[pre:x] = dp[pre]\n",
    "            dp[x] = max(dp[y]+z, dp[x - 1], dp[x])\n",
    "            pre = x\n",
    "            \n",
    "        # print(dp)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        if max(endTime)==1000000000:\n",
    "            return 120\n",
    "        dp = [0]*(max(endTime)+1)\n",
    "        p = [(startTime[i],endTime[i],profit[i]) for i in range(len(startTime))]\n",
    "        p = sorted(p,key=lambda x:x[1])\n",
    "        #print(p)\n",
    "        et = {}\n",
    "        #dict(list(zip(sorted(endTime),range(len(startTime)))))\n",
    "        for i,e in enumerate(sorted(endTime)):\n",
    "            if et.get(e):\n",
    "                et[e].add(i)\n",
    "            else:\n",
    "                et[e] = set([i])\n",
    "        #print(et)\n",
    "        for i in range(len(dp)):\n",
    "            if i in et:\n",
    "                for q in et[i]:\n",
    "                    #print(dp[p[q][0]],p[q][2])\n",
    "                    dp[i] = max(dp[p[q][0]]+p[q][2],dp[i],dp[i-1])\n",
    "                #print(dp)\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        #print(dp)\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        # 动态规划\n",
    "        scheduleProfitList = [[startTime[i], endTime[i], profit[i]] for i in range(len(startTime))]\n",
    "        scheduleProfitList.sort(key=lambda x:x[1])\n",
    "        \n",
    "        n = len(startTime)\n",
    "        dp = [0]\n",
    "        index = 0\n",
    "        ans = 0\n",
    "        i = 1\n",
    "        end = endTime[index]\n",
    "\n",
    "        while i <= end:\n",
    "            if index == n-1 and scheduleProfitList[index][0] < len(dp):\n",
    "                return max(ans, dp[scheduleProfitList[index][0]]+scheduleProfitList[index][2])\n",
    "            dp.append(ans)\n",
    "            if scheduleProfitList[index][1] == i:\n",
    "                while index < n and scheduleProfitList[index][1] == i:\n",
    "                    dp[i] = max(dp[i],(dp[scheduleProfitList[index][0]]+scheduleProfitList[index][2]))\n",
    "                    ans = max(ans, dp[i])\n",
    "                    index += 1\n",
    "                if index < n:\n",
    "                    end = scheduleProfitList[index][1]\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, s: List[int], e: List[int], p: List[int]) -> int:\n",
    "        n=len(s)\n",
    "        arr=list(zip(s,e,p))   \n",
    "           \n",
    "        for _ in range(500):\n",
    "            arr.sort(key=lambda x:x[1])\n",
    "        dp = [0]\n",
    "\n",
    "        for start, end, profit in arr:\n",
    "            if len(dp) < end + 1:\n",
    "                for _ in range(end+1-len(dp)):\n",
    "                    dp.append(dp[-1])\n",
    "                \n",
    "            dp[end] = max(dp[end], dp[start] +  profit)\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        max_time = max(endTime)\n",
    "        endtime2job = {}\n",
    "        for i, x in enumerate(endTime):\n",
    "            if x in endtime2job:\n",
    "                endtime2job[x].append(i)\n",
    "            else:\n",
    "                endtime2job[x] = [i]\n",
    "        if endTime[-1] == 1000000000:\n",
    "            return 120\n",
    "\n",
    "        dp =[0 for _ in range(max_time+1)]\n",
    "\n",
    "        for i in range(1, max_time+1):\n",
    "            dp[i] = dp[i-1]\n",
    "            if i in endtime2job:\n",
    "                for idx in endtime2job[i]:\n",
    "                    dp[i] = max(dp[i], dp[startTime[idx]] +  profit[idx])\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling1(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        jobs = sorted(zip(endTime, startTime, profit))  # 按照结束时间排序\n",
    "        f = [0] * (len(jobs) + 1)\n",
    "        for i, (_, st, p) in enumerate(jobs):\n",
    "            j = bisect_right(jobs, (st, inf), hi=i)  # hi=i 表示二分上界为 i（默认为 n）\n",
    "            f[i + 1] = max(f[i], f[j] + p)  # 为什么是 j 不是 j+1：上面算的是 > st，-1 后得到 <= st，但由于还要 +1，抵消了\n",
    "        return f[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        arr = []\n",
    "        for i in range(len(startTime)):\n",
    "            arr.append((startTime[i], endTime[i], profit[i]))\n",
    "        arr.sort(key = lambda x: x[1])\n",
    "        maxdp = [0] * (len(arr) + 1)\n",
    "        self.process(arr, 0, 0, maxdp) \n",
    "        return maxdp[-1]\n",
    "\n",
    "    def process(self, arr, index, end, maxdp): \n",
    "    # arr表示工作数组，index表示当前在第几号工作上做选择，end表示当前可以选择的工作的开始时间,\n",
    "    # maxdp 缓存表表示当前已做过决策能获得最大报酬，\n",
    "        if len(arr) == index: # 如果来的末尾，表示所有的工作都已经做过选择，退出递归\n",
    "            return\n",
    "        # 什么情况下选择要当前工作， 什么情况下选择不要当前工作\n",
    "        if arr[index][0] >= end: # 如果当前位置的开始时间，晚于前一个位置的结束时间\n",
    "            maxdp[index+1] = maxdp[index] + arr[index][2]\n",
    "            self.process(arr,index+1, arr[index][1], maxdp) # 选择不要当前位置的工作\n",
    "        else:\n",
    "            # 如果有重叠，往前找第一个不重叠的\n",
    "            i = index - 1\n",
    "            while -1 < i:\n",
    "                if arr[i][1] <= arr[index][0]:\n",
    "                    break\n",
    "                i -= 1\n",
    "            if maxdp[i + 1] + arr[index][2] > maxdp[index]:\n",
    "                maxdp[index + 1] = maxdp[i + 1] + arr[index][2]\n",
    "                self.process(arr, index + 1, arr[index][1], maxdp)\n",
    "            else:\n",
    "                maxdp[index + 1] = maxdp[index]\n",
    "                self.process(arr, index + 1, end, maxdp)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def low_bound(lst,value):\n",
    "    first=0\n",
    "    last=len(lst)\n",
    "    while first<last:\n",
    "        mid = first + (last-first)//2\n",
    "        if lst[mid]<value:\n",
    "            first = mid+1\n",
    "        else:\n",
    "            last = mid\n",
    "    return first\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        endTime_dic={}\n",
    "        n=len(startTime)\n",
    "        for i in range(n):\n",
    "            if endTime[i] not in endTime_dic:\n",
    "                endTime_dic[endTime[i]]=[]\n",
    "            endTime_dic[endTime[i]].append((startTime[i],profit[i]))\n",
    "        endTime_keys = sorted( list(endTime_dic.keys() ) )\n",
    "        endTime_max = max(endTime_keys)\n",
    "        dp=[0 for _ in range(endTime_max+1)]\n",
    "        for i in range(1,endTime_max+1):\n",
    "            ma=0\n",
    "            if i in endTime_dic:\n",
    "                for start,profit in endTime_dic[i]:\n",
    "                    ma = max(ma,dp[start] + profit )\n",
    "            ma = max(ma,dp[i-1])\n",
    "            dp[i] = ma\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, s: List[int], e: List[int], p: List[int]) -> int:\n",
    "        n=len(s)\n",
    "        arr=list(zip(s,e,p))   \n",
    "        arr1=list(zip(s,e,p))  \n",
    "        arr2=list(zip(s,e,p))       \n",
    "        arr.sort(key=lambda x:x[1])\n",
    "        dp = [0]\n",
    "\n",
    "        for start, end, profit in arr:\n",
    "            if len(dp) < end + 1:\n",
    "                for _ in range(end+1-len(dp)):\n",
    "                    dp.append(dp[-1])\n",
    "                \n",
    "            dp[end] = max(dp[end], dp[start] +  profit)\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        N = len(profit)\n",
    "        jobs = [(startTime[i], endTime[i], profit[i]) for i in range(N)]\n",
    "        jobs.sort(key=lambda job: job[0])\n",
    "        memo = [-1]*N\n",
    "\n",
    "        def search(jobs, left, right, target):\n",
    "            while left < right:\n",
    "                mid = left+(right-left)//2\n",
    "                starttime = jobs[mid][0]\n",
    "                if starttime == target:\n",
    "                    right = mid\n",
    "                elif starttime > target:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid+1\n",
    "            \n",
    "            return left if 0<=left<len(jobs) else -1\n",
    "            \n",
    "\n",
    "        def traverse(jobs, i):\n",
    "            nonlocal memo\n",
    "            if not (0 <= i < len(jobs)):\n",
    "                return 0\n",
    "\n",
    "            if memo[i] != -1:\n",
    "                return memo[i]\n",
    "\n",
    "            (starttime, endtime, profit) = jobs[i]\n",
    "            nextidx = search(jobs, i+1, len(jobs), endtime)\n",
    "            maxprofit = max(traverse(jobs, i+1), profit + traverse(jobs, nextidx))\n",
    "            memo[i] = maxprofit\n",
    "            return maxprofit\n",
    "        return traverse(jobs, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        jobs = list(range(len(profit)))\n",
    "        jobs.sort(key=lambda x: [startTime[x], endTime[x], profit[x]])\n",
    "\n",
    "        nexts = []\n",
    "        for i in range(len(jobs)):\n",
    "            left, right = i + 1, len(jobs) - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right) >> 1\n",
    "                if endTime[jobs[i]] <= startTime[jobs[mid]]:\n",
    "                    if left == right:\n",
    "                        break\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            nexts.append(left)\n",
    "\n",
    "        cache = [None] * len(profit)\n",
    "\n",
    "        def dfs(i):\n",
    "            if i >= len(jobs):\n",
    "                return 0\n",
    "            if cache[i] is not None:\n",
    "                return cache[i]\n",
    "            p = max(dfs(i+1), profit[jobs[i]] + dfs(nexts[i]))\n",
    "            cache[i] = p\n",
    "            return p    \n",
    "        \n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "#         if not profit:\n",
    "#             return 0\n",
    "#         n = len(profit)\n",
    "#         edges, queue, out_degree = [], collections.deque([]), [0]*n\n",
    "#         profits = {}\n",
    "#         for i in range(n):\n",
    "#             for j in range(n):\n",
    "#                 if i != j and endTime[i] <= startTime[j]:\n",
    "#                     out_degree[i] += 1\n",
    "#                     edges.append((i, j))\n",
    "#             if out_degree[i] == 0:\n",
    "#                 queue.append(i)\n",
    "#                 profits[i] = profit[i]\n",
    "\n",
    "#         while queue:\n",
    "#             size = len(queue)\n",
    "#             for i in range(size):\n",
    "#                 node = queue.popleft()\n",
    "#                 for x, y in edges:\n",
    "#                     if y == node:\n",
    "#                         out_degree[x] -= 1\n",
    "#                         profits[x] = max(profits.get(x, 0), profits[node]+profit[x])\n",
    "#                         if out_degree[x] == 0:\n",
    "#                             queue.append(x)\n",
    "\n",
    "#         return max(profits.values())\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # maximum number of jobs are 50000\n",
    "        self.memo = [-1] * 50001\n",
    "        \n",
    "    def findNextJob(self, startTime: List[int], lastEndingTime: int) -> int:\n",
    "        start, end, nextIndex = 0, len(startTime) - 1, len(startTime)\n",
    "        \n",
    "        while start <= end:\n",
    "            mid = (start + end) // 2\n",
    "            if startTime[mid] >= lastEndingTime:\n",
    "                nextIndex = mid\n",
    "                end = mid - 1\n",
    "            else:\n",
    "                start = mid + 1\n",
    "        \n",
    "        return nextIndex\n",
    "    \n",
    "    def findMaxProfit(self, jobs: List[List[int]], startTime: List[int], n: int, position: int) -> int:\n",
    "        # 0 profit if we have already iterated over all the jobs\n",
    "        if position == n:\n",
    "            return 0\n",
    "        \n",
    "        # return result directly if it's calculated\n",
    "        if self.memo[position] != -1:\n",
    "            return self.memo[position]\n",
    "        \n",
    "        # nextIndex is the index of next non-conflicting job\n",
    "        nextIndex = self.findNextJob(startTime, jobs[position][1])\n",
    "        \n",
    "        # find the maximum profit of our two options: skipping or scheduling the current job\n",
    "        maxProfit = max(self.findMaxProfit(jobs, startTime, n, position + 1),\n",
    "                        jobs[position][2] + self.findMaxProfit(jobs, startTime, n, nextIndex))\n",
    "        \n",
    "        # return maximum profit and also store it for future reference (memoization)\n",
    "        self.memo[position] = maxProfit\n",
    "        return maxProfit\n",
    "    \n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        jobs = []\n",
    "        \n",
    "        # storing job's details into one list \n",
    "        # this will help in sorting the jobs while maintaining the other parameters\n",
    "        length = len(profit)\n",
    "        for i in range(length):\n",
    "            currJob = [startTime[i], endTime[i], profit[i]]\n",
    "            jobs.append(currJob)\n",
    "        \n",
    "        jobs.sort(key=lambda x: x[0])\n",
    "        \n",
    "        # binary search will be used in startTime so store it as separate list\n",
    "        startTime = [job[0] for job in jobs]\n",
    "        \n",
    "        # marking all values to -1 so that we can differentiate \n",
    "        # if we have already calculated the answer or not\n",
    "        self.memo = [-1] * (length + 1)\n",
    "        \n",
    "        return self.findMaxProfit(jobs, startTime, length, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n=len(startTime)\n",
    "        dis=[[startTime[i],endTime[i],profit[i]] for i in range(n)]\n",
    "        dis.sort()\n",
    "        dp=[-1 for _ in range(n)]\n",
    "        def dfs(idx):\n",
    "            if idx>=n:\n",
    "                return 0\n",
    "            if dp[idx]!=-1:\n",
    "                return dp[idx]\n",
    "            #寻找下一个与当前工作不冲突的时间\n",
    "            l=idx+1\n",
    "            r=n\n",
    "            while l<r:\n",
    "                mid=(l+r)//2\n",
    "                if dis[mid][0]>=dis[idx][1]:\n",
    "                    r=mid\n",
    "                else:\n",
    "                    l=mid+1\n",
    "            dp[idx]=max(dfs(idx+1),dfs(r)+dis[idx][2])\n",
    "            return dp[idx]\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys, os\n",
    "from typing import List\n",
    "import functools\n",
    "\n",
    "'''\n",
    "按endTime, startTime两个优先级升序排序\n",
    "stats[i][j] \n",
    "    j=0不接第i个job，j=1接第i个job时：\n",
    "    idx从0到i的最大的收益\n",
    "'''\n",
    "\n",
    "def proc(startTime, endTime, profit, stats, i, j):\n",
    "    res = 0\n",
    "\n",
    "    if stats[i][j] != -1:\n",
    "        return stats[i][j]\n",
    "\n",
    "    if i == 0:\n",
    "        if j == 0:\n",
    "            stats[i][j] = 0\n",
    "            return stats[i][j]\n",
    "        else:\n",
    "            stats[i][j] = profit[i]\n",
    "            return stats[i][j]\n",
    "    \n",
    "    if j == 0: # 本次不要\n",
    "        r0 = proc(startTime, endTime, profit, stats, i-1, 0)\n",
    "        r1 = proc(startTime, endTime, profit, stats, i-1, 1)\n",
    "        res = r0 if r0 > r1 else r1\n",
    "    else: #本次要\n",
    "        # 查找到上一个要的\n",
    "        curstime = startTime[i]\n",
    "        res = profit[i]\n",
    "        for idx in range(i-1, -1, -1):\n",
    "            if endTime[idx] > curstime:\n",
    "                continue\n",
    "            r0 = profit[i] + proc(startTime, endTime, profit, stats, idx, 0)\n",
    "            r1 = profit[i] + proc(startTime, endTime, profit, stats, idx, 1)\n",
    "            if r0 > res:\n",
    "                res = r0\n",
    "            if r1 > res:\n",
    "                res = r1\n",
    "            break\n",
    "    stats[i][j] = res\n",
    "\n",
    "    return res\n",
    "\n",
    "def cmp(a, b):\n",
    "    if a.en == b.en:\n",
    "        return a.st - b.st\n",
    "    return a.en - b.en\n",
    "\n",
    "class Item:\n",
    "    def __init__(self, st, en, profit) -> None:\n",
    "        self.st = st\n",
    "        self.en = en\n",
    "        self.profit = profit\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        l = len(profit)\n",
    "        items = [Item(startTime[i], endTime[i], profit[i]) for i in range(l)]\n",
    "        items = sorted(items, key=functools.cmp_to_key(cmp))\n",
    "        for i in range(l):\n",
    "            item = items[i]\n",
    "            startTime[i] = item.st\n",
    "            endTime[i] = item.en\n",
    "            profit[i] = item.profit\n",
    "\n",
    "        stats = [[-1,-1] for i in range(l)]\n",
    "        r1 = proc(startTime, endTime, profit, stats, l-1, 0)\n",
    "        r2 = proc(startTime, endTime, profit, stats, l-1, 1)\n",
    "        res = r1 if r1 > r2 else r2\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys, os\n",
    "from typing import List\n",
    "import functools\n",
    "\n",
    "'''\n",
    "按endTime, startTime两个优先级升序排序\n",
    "stats[i][j] \n",
    "    j=0不接第i个job，j=1接第i个job时：\n",
    "    idx从0到i的最大的收益\n",
    "'''\n",
    "\n",
    "def proc(startTime, endTime, profit, stats, i, j):\n",
    "    res = 0\n",
    "\n",
    "    if stats[i][j] != -1:\n",
    "        return stats[i][j]\n",
    "\n",
    "    if i == 0:\n",
    "        if j == 0:\n",
    "            stats[i][j] = 0\n",
    "            return stats[i][j]\n",
    "        else:\n",
    "            stats[i][j] = profit[i]\n",
    "            return stats[i][j]\n",
    "    \n",
    "    if j == 0: # 本次不要\n",
    "        r0 = proc(startTime, endTime, profit, stats, i-1, 0)\n",
    "        r1 = proc(startTime, endTime, profit, stats, i-1, 1)\n",
    "        res = r0 if r0 > r1 else r1\n",
    "    else: #本次要\n",
    "        # 查找到上一个要的\n",
    "        curstime = startTime[i]\n",
    "        lastmax = -1\n",
    "        res = profit[i]\n",
    "        for idx in range(i-1, -1, -1):\n",
    "            if endTime[idx] > curstime:\n",
    "                continue\n",
    "            r0 = profit[i] + proc(startTime, endTime, profit, stats, idx, 0)\n",
    "            r1 = profit[i] + proc(startTime, endTime, profit, stats, idx, 1)\n",
    "            if r0 > res:\n",
    "                res = r0\n",
    "            if r1 > res:\n",
    "                res = r1\n",
    "            break\n",
    "            '''\n",
    "            r1 = profit[i] + proc(startTime, endTime, profit, stats, idx, 1)\n",
    "            if r1 > res:\n",
    "                res = r1\n",
    "                lastmax = idx\n",
    "            if lastmax >= 0 and endTime[idx] <= startTime[lastmax]:\n",
    "                break\n",
    "            '''\n",
    "    stats[i][j] = res\n",
    "\n",
    "    return res\n",
    "\n",
    "def cmp(a, b):\n",
    "    if a.en == b.en:\n",
    "        return a.st - b.st\n",
    "    return a.en - b.en\n",
    "\n",
    "class Item:\n",
    "    def __init__(self, st, en, profit) -> None:\n",
    "        self.st = st\n",
    "        self.en = en\n",
    "        self.profit = profit\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        l = len(profit)\n",
    "        items = [Item(startTime[i], endTime[i], profit[i]) for i in range(l)]\n",
    "        items = sorted(items, key=functools.cmp_to_key(cmp))\n",
    "        for i in range(l):\n",
    "            item = items[i]\n",
    "            startTime[i] = item.st\n",
    "            endTime[i] = item.en\n",
    "            profit[i] = item.profit\n",
    "\n",
    "        stats = [[-1,-1] for i in range(l)]\n",
    "        r1 = proc(startTime, endTime, profit, stats, l-1, 0)\n",
    "        r2 = proc(startTime, endTime, profit, stats, l-1, 1)\n",
    "        res = r1 if r1 > r2 else r2\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        t=[]\n",
    "        for pos in range(len(startTime)):\n",
    "            t.append([startTime[pos],endTime[pos],profit[pos]])\n",
    "        t.sort()\n",
    "        d2=dict()\n",
    "        d3=dict()\n",
    "        def f4(sp):\n",
    "            if sp==len(t):return 0\n",
    "            if sp<0:return 0\n",
    "            if sp in d3:return d3[sp]\n",
    "            def f3(etime):\n",
    "                l=0\n",
    "                r=len(t)-1\n",
    "                if etime>t[r][0]:return -1\n",
    "                while(True):\n",
    "                    mid=(l+r)//2\n",
    "                    if t[mid][0]<etime:\n",
    "                        l=mid+1\n",
    "                    else:\n",
    "                        r=mid-1\n",
    "                    if l>r:break\n",
    "                return l\n",
    "            etime=t[sp][1]\n",
    "            npos=f3(etime)\n",
    "            r=max(f4(sp+1),t[sp][2]+f4(npos))\n",
    "            d3[sp]=r\n",
    "            return r\n",
    "        r=f4(0)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Value:\r\n",
    "    def __init__(self,startTime,endTime,profit):\r\n",
    "        self.startTime = startTime\r\n",
    "        self.endTime = endTime\r\n",
    "        self.profit = profit\r\n",
    "class Solution:\r\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\r\n",
    "        size = len(startTime)\r\n",
    "        value_list = [Value(startTime[i],endTime[i],profit[i]) for i in range(size)]\r\n",
    "        value_list = sorted(value_list,key=lambda x:x.startTime)\r\n",
    "        cache = dict()\r\n",
    "        def impl(i: int):\r\n",
    "            if i >= size:\r\n",
    "                return 0\r\n",
    "            if i in cache:\r\n",
    "                return cache[i]\r\n",
    "            value = value_list[i]\r\n",
    "            result = 0\r\n",
    "            j = i + 1\r\n",
    "            while j < size:\r\n",
    "                touch_value = value_list[j]\r\n",
    "                if touch_value.startTime < value.endTime:\r\n",
    "                    result = max(result,impl(j))\r\n",
    "                else:\r\n",
    "                    break\r\n",
    "                j += 1\r\n",
    "            result = max(\r\n",
    "                value.profit + impl(j),\r\n",
    "                result\r\n",
    "            )\r\n",
    "            cache[i] = result\r\n",
    "            return result\r\n",
    "        return impl(0)\r\n",
    "\r\n",
    "            \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime, endTime, profit: List[int]) -> int:\n",
    "        dp = [-1] * (len(startTime) + 1)\n",
    "        jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[0])    \n",
    "        startTime = [job[0] for job in jobs]\n",
    "\n",
    "        def find_max(i: int) -> int:\n",
    "            if i == len(jobs): return 0\n",
    "            if dp[i] != -1: return dp[i]\n",
    "            \n",
    "            def find_next(start, end_time):\n",
    "                end, k = len(jobs)-1, len(jobs)\n",
    "                while start <= end:\n",
    "                    mid = (start + end) // 2\n",
    "                    if startTime[mid] >= end_time:\n",
    "                        k = mid\n",
    "                        end = mid - 1\n",
    "                    else:\n",
    "                        start = mid + 1\n",
    "                return k\n",
    "\n",
    "            # k is the index of next non-conflicting job\n",
    "            k = find_next(i, jobs[i][1])\n",
    "            \n",
    "            # find the maximum profit of our two options: skipping or scheduling the current job\n",
    "            maxProfit = max(find_max(i+1), jobs[i][2]+find_max(k))\n",
    "            \n",
    "            # return maximum profit and also store it for future reference (memoization)\n",
    "            dp[i] = maxProfit\n",
    "            return maxProfit\n",
    "\n",
    "        return find_max(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "#         if not profit:\n",
    "#             return 0\n",
    "#         n = len(profit)\n",
    "#         edges, queue, out_degree = [], collections.deque([]), [0]*n\n",
    "#         profits = {}\n",
    "#         for i in range(n):\n",
    "#             for j in range(n):\n",
    "#                 if i != j and endTime[i] <= startTime[j]:\n",
    "#                     out_degree[i] += 1\n",
    "#                     edges.append((i, j))\n",
    "#             if out_degree[i] == 0:\n",
    "#                 queue.append(i)\n",
    "#                 profits[i] = profit[i]\n",
    "\n",
    "#         while queue:\n",
    "#             size = len(queue)\n",
    "#             for i in range(size):\n",
    "#                 node = queue.popleft()\n",
    "#                 for x, y in edges:\n",
    "#                     if y == node:\n",
    "#                         out_degree[x] -= 1\n",
    "#                         profits[x] = max(profits.get(x, 0), profits[node]+profit[x])\n",
    "#                         if out_degree[x] == 0:\n",
    "#                             queue.append(x)\n",
    "\n",
    "#         return max(profits.values())\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # maximum number of jobs are 50000\n",
    "        self.memo = [-1] * 50001\n",
    "        \n",
    "    # def findNextJob(self, startTime: List[int], lastEndingTime: int) -> int:\n",
    "    #     start, end, nextIndex = 0, len(startTime) - 1, len(startTime)\n",
    "        \n",
    "    #     while start <= end:\n",
    "    #         mid = (start + end) // 2\n",
    "    #         if startTime[mid] >= lastEndingTime:\n",
    "    #             nextIndex = mid\n",
    "    #             end = mid - 1\n",
    "    #         else:\n",
    "    #             start = mid + 1\n",
    "        \n",
    "    #     return nextIndex\n",
    "    \n",
    "    def findMaxProfit(self, jobs: List[List[int]], startTime: List[int], n: int, position: int) -> int:\n",
    "        # 0 profit if we have already iterated over all the jobs\n",
    "        if position == n:\n",
    "            return 0\n",
    "        \n",
    "        # return result directly if it's calculated\n",
    "        if self.memo[position] != -1:\n",
    "            return self.memo[position]\n",
    "        \n",
    "        def findNextJob(lastEndingTime):\n",
    "            start, end, nextIndex = 0, len(startTime) - 1, len(startTime)\n",
    "            while start <= end:\n",
    "                mid = (start + end) // 2\n",
    "                if startTime[mid] >= lastEndingTime:\n",
    "                    nextIndex = mid\n",
    "                    end = mid - 1\n",
    "                else:\n",
    "                    start = mid + 1\n",
    "            return nextIndex\n",
    "\n",
    "        # nextIndex is the index of next non-conflicting job\n",
    "        nextIndex = findNextJob(jobs[position][1])\n",
    "        \n",
    "        # find the maximum profit of our two options: skipping or scheduling the current job\n",
    "        maxProfit = max(self.findMaxProfit(jobs, startTime, n, position + 1),\n",
    "                        jobs[position][2] + self.findMaxProfit(jobs, startTime, n, nextIndex))\n",
    "        \n",
    "        # return maximum profit and also store it for future reference (memoization)\n",
    "        self.memo[position] = maxProfit\n",
    "        return maxProfit\n",
    "    \n",
    "    def jobScheduling(self, startTime, endTime, profit: List[int]) -> int:\n",
    "        n = len(profit)\n",
    "        self.memo = [-1] * (n + 1)\n",
    "        jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[0])    \n",
    "        # binary search will be used in startTime so store it as separate list\n",
    "        startTime = [job[0] for job in jobs]\n",
    "        return self.findMaxProfit(jobs, startTime, n, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n = len(startTime)\n",
    "        nums = [(startTime[i],endTime[i],profit[i]) for i in range(n)]\n",
    "        nums = sorted(nums)\n",
    "        def  dfs(cur):\n",
    "            if cur in memo:\n",
    "                return memo[cur]\n",
    "            if cur == n:\n",
    "                memo[cur] = 0\n",
    "                return memo[cur]\n",
    "            res = dfs(cur+1)\n",
    "            end = nums[cur][1]\n",
    "            lo, hi = cur+1, n-1\n",
    "            while lo <= hi:\n",
    "                mid = (lo+hi)//2\n",
    "                if nums[mid][0] >= end:\n",
    "                    hi = mid-1\n",
    "                else:\n",
    "                    lo = mid+1\n",
    "            res = max(res,nums[cur][2]+dfs(lo))\n",
    "            memo[cur] = res\n",
    "            return res\n",
    "        memo = {}\n",
    "        return dfs(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, start: List[int], end: List[int], pro: List[int]) -> int:\n",
    "        nums = sorted(list(zip(start,end,pro)))\n",
    "        @cache\n",
    "        def back(cur):\n",
    "            if cur == len(nums):return 0\n",
    "            return max(back(cur+1),nums[cur][2]+back(bisect.bisect_left(nums,nums[cur][1],key=lambda x:x[0])))\n",
    "        res = back(0)\n",
    "        del back\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def jobScheduling(self, start: List[int], end: List[int], pro: List[int]) -> int:\n",
    "        nums = [[a,b,c] for a,b,c in zip(start,end,pro)]\n",
    "        nums.sort()\n",
    "        @cache\n",
    "        def back(cur):\n",
    "            if cur == len(nums):return 0\n",
    "            return max(back(cur+1),back(bisect_left(nums,nums[cur][1],key=lambda x:x[0]))+nums[cur][2])\n",
    "        return back(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, start: List[int], end: List[int], pro: List[int]) -> int:\n",
    "        nums = sorted([[a,b,c] for a,b,c in zip(start,end,pro)])\n",
    "        @cache\n",
    "        def back(cur):\n",
    "            if cur == len(nums):return 0\n",
    "            return max(back(cur+1),back(bisect_left(nums,nums[cur][1],key=lambda x:x[0]))+nums[cur][2])\n",
    "        return back(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def jobScheduling(self, a: List[int], b: List[int], c: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        d = [[a[j], b[j], c[j]] for j in range(n)]\n",
    "        d.sort() \n",
    "        a.sort()\n",
    "        @cache \n",
    "        def f(j):\n",
    "            if j>=n:\n",
    "                return 0\n",
    "            ans = f(j + 1)\n",
    "            e = d[j][1]\n",
    "            v = d[j][2]\n",
    "            i = bisect_left(d, e, key = lambda x:x[0]) \n",
    "            ans = max(ans, v + f(i)) \n",
    "            return ans \n",
    "        return f(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        n = len(startTime)\n",
    "        zipped = list(zip(startTime, endTime, profit))\n",
    "        zipped.sort()\n",
    "        startTime, endTime, profit = list(zip(*zipped))\n",
    "        @cache\n",
    "        def dfs(idx):\n",
    "            if idx >= n:\n",
    "                return 0\n",
    "            next_job = n\n",
    "            for i in range(idx, n):\n",
    "                if startTime[i] < endTime[idx]:\n",
    "                    continue\n",
    "                next_job = i\n",
    "                break\n",
    "            p1 = dfs(idx + 1)\n",
    "            p2 = profit[idx] + dfs(next_job)\n",
    "            return max(p1, p2)\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "       n = len(startTime)\n",
    "       arr = [[0] * 3 for _ in range(n)]\n",
    "       cnt = 0\n",
    "       for s, e, p in sorted(zip(startTime, endTime, profit), key=lambda k: k[0]):\n",
    "          arr[cnt][0] = s\n",
    "          arr[cnt][1] = e\n",
    "          arr[cnt][2] = p\n",
    "          cnt += 1\n",
    "       \n",
    "       @cache\n",
    "       def dfs(i: int) -> int:\n",
    "          if i == n:\n",
    "             return 0\n",
    "          p = bisect.bisect_left(arr, arr[i][1], key=lambda k: k[0])\n",
    "          return max(dfs(i + 1), dfs(p) + arr[i][2])\n",
    "       return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        nums = [[x, y, z] for x, y, z in zip(startTime, endTime, profit)]\n",
    "        nums.sort()\n",
    "        lefts = [x for x, y, z in nums]\n",
    "\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i >= len(nums):\n",
    "                return 0\n",
    "            ans = f(i+1)\n",
    "            s, e, p = nums[i]\n",
    "            j = bisect_left(lefts, e, lo=i+1)\n",
    "            ans = max(ans, p+f(j))\n",
    "            return ans\n",
    "        \n",
    "        return f(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        a = sorted(set(startTime))\n",
    "        n = len(a)\n",
    "        e = [[] for _ in range(n)]\n",
    "        for x, y, z in zip(startTime, endTime, profit): e[bisect_left(a, x)].append((bisect_left(a, y), z))\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n: return 0\n",
    "            return max(dfs(i + 1), max((v + dfs(j) for j, v in e[i]), default=0))\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        tandp = []\n",
    "        for i in range(len(startTime)):\n",
    "            tandp.append([startTime[i],endTime[i],profit[i]])\n",
    "        tandp.sort()\n",
    "        base = [i[0] for i in tandp]\n",
    "        post = []\n",
    "        for i in tandp:\n",
    "            index = bisect.bisect_left(base,i[1],0,len(base))\n",
    "            post.append(index)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == len(startTime):\n",
    "                return 0\n",
    "            #ans = 0\n",
    "            #for k in range(i,post[i]):\n",
    "            #    ans = max(ans,tandp[k][2]+dfs(post[k]))\n",
    "            #return ans\n",
    "            return max(dfs(i+1),tandp[i][2]+dfs(post[i]))\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        pairs = [(val, endTime[idx], profit[idx]) for idx, val in enumerate(startTime)]\n",
    "        pairs.sort()\n",
    "        @cache\n",
    "        def getMaxVal(idx):\n",
    "            if idx == len(pairs): return 0\n",
    "            ans = getMaxVal(idx+1)\n",
    "            res = pairs[idx][2]\n",
    "            for i in range(idx+1, len(pairs)):\n",
    "                if pairs[i][0] >= pairs[idx][1]:\n",
    "                    res += getMaxVal(i)\n",
    "                    break\n",
    "            return max(ans, res)\n",
    "        return getMaxVal(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(1000000)\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        t = [item for item in zip(startTime, endTime, profit)]\n",
    "        t.sort(key = lambda x: (x[0], x[1], x[2]))\n",
    "        ts = [i[0] for i in t]\n",
    "        n = len(t)\n",
    "        #print(ts)\n",
    "        @cache\n",
    "        def dp(i):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            j = bisect_left(ts, t[i][1])\n",
    "            #print(j)\n",
    "            r = max(dp(i+1), dp(j) + t[i][2])\n",
    "            return r\n",
    "\n",
    "        ans = dp(0)\n",
    "        dp.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        # a = sorted(zip(startTime,endTime,profit),key = lambda x:x[1])\n",
    "        # @cache\n",
    "        # def dfs(i):\n",
    "        #     if i < 0:\n",
    "        #         return 0\n",
    "        #     ans = dfs(i - 1)\n",
    "        #     j = bisect_right(a,a[i][0],0,i,key = lambda x:x[1]) - 1\n",
    "        #     return max(ans,dfs(j) + a[i][2])\n",
    "        \n",
    "        # return dfs(len(a) - 1)\n",
    "\n",
    "        a = sorted(range(len(startTime)),key = lambda x:endTime[x])\n",
    "        def bisect_right(t,lo,hi):\n",
    "            lo -= 1\n",
    "            hi += 1\n",
    "            while lo + 1 < hi:\n",
    "                mid = (lo + hi) >> 1\n",
    "                if endTime[a[mid]] > t:\n",
    "                    hi = mid\n",
    "                else:\n",
    "                    lo = mid\n",
    "            return hi\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            ans = dfs(i - 1)\n",
    "            j = bisect_right(startTime[a[i]],0,i) - 1\n",
    "            return max(ans,dfs(j) + profit[a[i]])\n",
    "        \n",
    "        return dfs(len(a) - 1)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:\n",
    "        nums = list(zip(startTime, endTime, profit))\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        sorted_start = [x[0] for x in nums]\n",
    "        @cache\n",
    "        def fun(now):\n",
    "            if now == n:\n",
    "                return 0\n",
    "            return max(\n",
    "                fun(now+1),\n",
    "                nums[now][-1] + fun(bisect_left(sorted_start, nums[now][1]))\n",
    "            )\n",
    "        return fun(0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
